package edu.rpi.cs.webgraph.graphfragment;

import edu.uci.ics.jung.algorithms.generators.GraphGenerator;
import edu.uci.ics.jung.algorithms.generators.random.EppsteinPowerLawGenerator;
import edu.uci.ics.jung.graph.DirectedSparseGraph;
import edu.uci.ics.jung.graph.Graph;
import edu.uci.ics.jung.graph.util.Pair;
import org.apache.commons.collections15.Factory;

import java.util.Collection;
import java.util.Random;

/**
 * Author: josh
 * Date: Mar 19, 2009
 * Time: 7:30:15 PM
 */
public class GraphUtils {
    private static final Random RANDOM = new Random();

    public static <V, E> Graph<V, E> randomSubgraphByEdges(final Graph<V, E> originalGraph,
                                                           final double edgeProbability,
                                                           final Factory<Graph<V, E>> graphFactory) {
        Graph<V, E> subgraph = graphFactory.create();

        // Provisionally add all vertices.
        for (V v : originalGraph.getVertices()) {
            subgraph.addVertex(v);
        }

        // Randomly copy some edges.
        for (E e : originalGraph.getEdges()) {
            if (RANDOM.nextDouble() < edgeProbability) {
                Pair<V> endpoints = originalGraph.getEndpoints(e);
                subgraph.addEdge(e, endpoints.getFirst(), endpoints.getSecond());
            }
        }

        // Remove orphan vertices.
        for (V v : originalGraph.getVertices()) {
            if (0 == subgraph.getNeighbors(v).size()) {
                subgraph.removeVertex(v);
            }
        }

        return subgraph;
    }

    public static <V, E> Graph<V, E> randomSubgraphByVertices(final Graph<V, E> originalGraph,
                                                              final double vertexProbability,
                                                              final Factory<Graph<V, E>> graphFactory) {
        Graph<V, E> subgraph = graphFactory.create();

        // Randomly add some vertices.
        for (V v : originalGraph.getVertices()) {
            if (RANDOM.nextDouble() < vertexProbability) {
                subgraph.addVertex(v);
            }
        }

        // Copy all edges with vertices already added to subgraph.
        for (E e : originalGraph.getEdges()) {
            Pair<V> endpoints = originalGraph.getEndpoints(e);
            if (subgraph.getVertices().contains(endpoints.getFirst())
                    && subgraph.getVertices().contains(endpoints.getSecond())) {
                subgraph.addEdge(e, endpoints.getFirst(), endpoints.getSecond());
            }
        }

        return subgraph;
    }

    public static <V, E> boolean isSubgraphOf(final Graph<V, E> subgraph,
                                              final Graph<V, E> parentGraph) {
        for (E e : subgraph.getEdges()) {
            Pair<V> endpoints = subgraph.getEndpoints(e);

            Collection<E> parentEdges = parentGraph.findEdgeSet(endpoints.getFirst(), endpoints.getSecond());
            boolean found = false;
            for (E pe : parentEdges) {
                // TODO: perform some comparison on e and pe
                found = true;
                continue;
            }
            if (!found) {
                return false;
            }
        }

        return true;
    }

    public static Graph<Integer, String> generateRandomGraph(final int nVertices,
                                                             final int nEdges,
                                                             final int edgesPerIteration) {
        //System.out.println("generating random graph with " + nVertices + " vertices, " + nEdges + " edges, and " + edgesPerIteration + " edges per iteration");
        Factory<Graph<Integer, String>> graphFactory
                = new Factory<Graph<Integer, String>>() {

            public Graph<Integer, String> create() {
                return new DirectedSparseGraph<Integer, String>();
            }
        };

        Factory<Integer> vertexFactory = new Factory<Integer>() {
            private int cur = 0;

            public Integer create() {
                return ++cur;
            }
        };

        // TODO: edge labels may not be needed (thus consume more memory than necessary).
        Factory<String> edgeFactory = new Factory<String>() {
            private int cur = 0;

            public String create() {
                return "e" + ++cur;
            }
        };

        GraphGenerator<Integer, String> gen
                = new EppsteinPowerLawGenerator<Integer, String>(
                graphFactory, vertexFactory, edgeFactory,
                nVertices, nEdges, nEdges / edgesPerIteration);
        Graph<Integer, String> graph = gen.create();

        return graph;
    }
}
